//public class Main {
//    public static void main(String[]args)throws Exception {
//        final Object obj = new Object();
//        Thread t1 = new Thread() {
//            public void run() {
//                synchronized (obj) {
//                    try {
//                        obj.wait();
//                        System.out.println("Thread 1 wake up.");
//                    } catch (InterruptedException e) {
//                    }
//                }
//            }
//        };
//        t1.start();
//        Thread.sleep(1000);//We assume thread 1 must start up within 1 sec.
//        Thread t2 = new Thread() {
//            public void run() {
//                synchronized (obj) {
//                    obj.notifyAll();
//                    System.out.println("Thread 2 sent notify.");
//                }
//            }
//        };
//        t2.start();
//    }
//}


//import java.util.Scanner;
//
//public class Main {
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        String line = scanner.next();
//        String[] numbers = line.split("/");
//        int a = Integer.parseInt(numbers[0]);
//        int b = Integer.parseInt(numbers[1]);
//        line = scanner.next();
//        numbers = line.split("/");
//        int c = Integer.parseInt(numbers[0]);
//        int d = Integer.parseInt(numbers[1]);
//
//
//    }
//}

class Solution1 {
    int n,m;
    int[][] dp;
    int[] xx = {1,-1,0,0};
    int[] yy = {0,0,1,-1};

    public int longestIncreasingPath(int[][] matrix) {
        n = matrix.length;
        m = matrix[0].length;
        int max = 1;
        dp = new int[n][m];
        for(int i =0 ;i <n; i++) {
            for(int j = 0; j<m; j++) {
                max = Math.max(max,dfs(matrix,i,j));
            }
        }
        return max;
    }

    //以x, y为起点的最长递增路径的长度
    public int dfs(int[][] matrix, int x, int y) {
        int max = 1;
        for(int i = 0; i<4; i++) {
            int dx = x + xx[i];
            int dy = y + yy[i];
            if(dx >= 0 && dx <n && dy >= 0 && dy <m && matrix[dx][dy] > matrix[x][y]) {
                if(dp[dx][dy] != 0) {
                    max = Math.max(max, 1+dp[dx][dy]);
                }else {
                    max = Math.max(max, 1+dfs(matrix,dx,dy));
                }
            }
        }
        dp[x][y] = max;
        return max;
    }
}


class Solution {
    int n,m;
    int[][] dp;
    int[] xx = {1,-1,0,0};
    int[] yy = {0,0,1,-1};

    public int longestIncreasingPath(int[][] matrix) {
        n = matrix.length;
        m = matrix[0].length;
        int max = 1;
        dp = new int[n][m];
        for(int i =0 ;i <n; i++) {
            for(int j = 0; j<m; j++) {
                max = Math.max(max,dfs(matrix,i,j));
            }
        }
        return max;
    }

    //以x, y为起点的最长递增路径的长度
    public int dfs(int[][] matrix, int x, int y) {
        if(dp[x][y]!=0) return dp[x][y];
        int max = 1;
        for(int i = 0; i<4; i++) {
            int dx = x + xx[i];
            int dy = y + yy[i];
            if(dx >= 0 && dx <n && dy >= 0 && dy <m && matrix[dx][dy] > matrix[x][y]) {
                max = Math.max(max, 1+dfs(matrix,dx,dy));
            }
        }
        dp[x][y] = max;
        return max;
    }
}